package com.leetcode.offer.chapter5;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/16 21:50
 */
public class MedianFinder_41 {

    // 大顶堆 + 小顶堆方式
    Queue<Integer> low;
    Queue<Integer> high;

    /**
     * initialize your data structure here.
     */
    public MedianFinder_41() {
        // 低位数用另一个优先队列存储
        // 保证从小到大
        low = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        high = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 第一次加入默认加到小顶堆
        if (low.size() == 0 && high.size() == 0) {
            low.offer(num);
            return;
        }

//
        if (low.size() == high.size()) {
            // 两者大小相同的时候，根据堆顶数据的大小执行入队
            if (low.peek() > num) low.offer(num);
            else high.offer(num);
        } else if (low.size() > high.size()) {
            // 当小顶堆数据较多时，如果num大于小顶堆堆顶数据，那么num直接加入大顶堆
            if (num > low.peek()) high.offer(num);
            else {
                // 否则需要执行一次大小顶堆的转换操作
                high.offer(low.poll());
                low.offer(num);
            }
        } else {
            if (num < high.peek()) low.offer(num);
            else {
                low.offer(high.poll());
                high.offer(num);
            }
        }
    }

    public double findMedian() {
        if (low.size() != high.size())
            return low.size() > high.size() ? low.peek() : high.peek();
        else
            return (low.peek() + high.peek()) / 2.0;
    }

}
